#pragma once

#include <algorithm>
#include <string>

namespace solution_043
{

class Solution
{
public:
    std::string multiply(std::string num1, std::string num2)
    {
        if (num1 == "0" || num2 == "0")
            return "0";

        std::reverse(num2.begin(), num2.end());
        std::string result;
        std::string product;
        for (int offset = 0; !num1.empty(); ++offset, num1.pop_back()) {
            if (num1.back() == '0')
                continue;
            product = num2;

            int c = 0;
            for (auto& ch : product) {
                int prod = (num1.back() - '0') * (ch - '0') + c;
                c = prod / 10;
                ch = prod % 10 + '0';
            }
            if (c > 0)
                product.push_back(c + '0');

            if (result.size() < product.size() + offset)
                result.resize(product.size() + offset, '0');

            c = 0;
            for (int i = 0; i < (int)product.size(); ++i) {
                int sum = (product[i] - '0') + (result[i + offset] - '0') + c;
                c = sum / 10;
                result[i + offset] = sum % 10 + '0';
            }
            if (c > 0)
                result.push_back(c + '0');
        }

        std::reverse(result.begin(), result.end());
        return result;
    }
};

}  /* namespace solution_043 */
